%%%-------------------------------------------------------------------
%%% File    : p219.erl
%%% Author  :  <>
%%% Description : 
%%%
%%% Created : 29 Nov 2008 by  <>

%% Let A and B be bit strings (sequences of 0's and 1's).
%% If A is equal to the leftmost length(A) bits of B,
%% then A is said to be a prefix of B.
%% For example, 00110 is a prefix of 001101001, but not 
%% of 00111 or 100110.
%% A prefix-free code of size n is a collection of n distinct 
%% bit strings such that no string is a prefix of any other. 
%% For example, this is a prefix-free code of size 6:
%% 0000, 0001, 001, 01, 10, 11
%% Now suppose that it costs one penny to transmit a '0' bit, 
%% but four pence to transmit a '1'.
%% Then the total cost of the prefix-free code shown above is 
%% 35 pence, which happens to be the cheapest possible for the
%% skewed pricing scheme in question.
%% In short, we write Cost(6) = 35.
%% What is Cost(10^(9)) ?

%%%-------------------------------------------------------------------
-module(p219).

%% API
-export([price/1, digits/1]).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------

generate(0) ->
    [];%C = 0 
generate(1) ->
    [<<0>>];%C= 1
generate(2) ->
    [<<0>>, <<1>>];%C= 5
generate(3) ->
    [<<0,0>>, <<0, 1>>, <<1>>];%C=11
generate(4) ->
    [<<0, 0, 0>>, <<0, 0, 1>>, <<0, 1>>, <<1>>]; %C=18
generate(5) ->
    [<<0, 0, 0, 0>>, <<0, 0, 0, 1>>, <<0, 0, 1>>, <<0, 1>>,  <<1>>];%C=26
generate(6) ->
    [<<0, 0, 0, 0, 0>>, <<0, 0, 0, 0, 1>>, <<0, 0, 0, 1>>, <<0, 0, 1>>, <<0, 1>>, <<1>>];%C=35
generate(7) ->
    [<<0, 0, 0, 0, 0>>, <<0, 0, 0, 0, 1>>, <<0, 0, 0, 1>>, <<0, 0, 1>>, <<0, 1>>, <<1, 0>>,  <<1, 1>>];%C=44
generate(8) ->
    [<<0, 0, 0, 0, 0>>, <<0, 0, 0, 0, 1>>, <<0, 0, 0, 1>>, <<0, 0, 0, 1>>, <<0, 0, 1>>, <<0, 1>>, <<1, 0>>,  <<1, 1>>].%C=44

price(0)->0;
price(1) -> 1;
price(2) -> 5;
price(3) -> 11;
price(4) -> 18;
price(5) -> 26;
price(N) when N > 5 ->
    CountRight = (N - 5) div 2,
    CountLeft = (N - 5) - CountRight,

    Price = fun(Count) -> 
                    (((Count + 8)*(Count + 9)) div 2) - 36
                end,
    io:format("~p/~p~n", [Price(CountLeft), Price(CountRight)]),
    Result = 26 + Price(CountLeft) + Price(CountRight),
    Result.

digits(N) ->
     digits(N, []).

digits(0, Acc) -> Acc;
digits(X, Acc) ->
    digits(X div 10, [X rem 10|Acc]).
%%====================================================================
%% Internal functions
%%====================================================================
